For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

Approaching a Design problem

DSA Interviews

• Problem statement is concrete - well defined
• Example input-output pairs
• Idea about the kind of solution that will work

• input constraints
• input: array of integers of size 10^6
• can you use a O(n^2) algo? No. Max O(n log n)

• Problem Statement
• Examples - solve it by hand
• Brute Force
• Draw observations
• Optimized

Design Interviews

• Problem statement is extremely vague
  "Design Typeahead"
• you might not even know what typeahead is
• interviews are very open ended

• discussion can go in any direction
• depends on your expertise
• depends on the interviewer's expertise

• interviews are still time constrained

• 45 mins

• you must

• what you're supposed to build
• figure out what the interviewer wants
• build that solution
• take sufficient complex things so that you can showcase your skills & impress the interviewer

The 5-step design approach

(20-25 mins)

• Problem Statement
• Functional Requirements
• Non-functional Requirements
• Scale Estimation

(25-20 mins)

• API Design
• System Design

Problem Statement

Reason by analogy

Find existing companies / systems that offer a similar product / feature.

Gives you an overview of the umbrella of different scopes that you can consider.

Typeahead is a specific form of autocomplete.

Try to type-ahead of the user

Typeahead in Google

Typeahead in Amazon

Typeahead & Search are different products

but typeahead is always followed by with some form of search.

What not to build

Autocomplete is available in many different settings

• Smartphone Keyboards: word completion  / contacts / ..
• Text editors / Code editors:

• intellisense: complete next token
• Github CoPilot: can show entire functions

• Grammarly: sentence completion while prose writing
• Gmail / Outlook:

• sentence completion for writing mail
• to/cc/bcc: email completion from contacts

Key difference b/w Typeahead & Autocomplete

Autocomplete is typically local to your machine. Any suggestions are specific to you. Autocomplete is standalone.

Typeahead is always associated with search.

The list of suggestions in typeahead are the most popular queries searched globally in the past, that match the given prefix.

Functional Requirements (FR)

Minimal Viable Product (MVP)

• Minimal: minimal set of features to achieve viability
• Viable: should demonstrate the core features & usability
• Product: solve a genuine problem

Actors

• End User: the person doing the google search

MVP Features

Always keep the "minimal" in your mind. MVP features is not a feature suggestion competition.

What to avoid

• anything that doesn't effect our backend infra / system design
• frontend features

• don't effect our backend infra / system design
• purely cosmetic

• common features that are not the core of the system that we're trying to build

• design Uber

• we require authentication
• is authentication what the interviewer is asking you to design
  no - it's just a dependency
• we require payments
• when the interviewer asks us to design Uber, they're not asking us to design payments
• we will assume that auth & payments already exist

• any suggested feature should come in the form of a complete sentence (from the user's perspective)

Hidden features

How to find hidden features?

For every feature that you discuss, think of the following

API (internal / user-facing)

typeahead(partial_query) => suggestions_list

user-facing

log_search(search_query) => void

internal

GET /typeahead?partialQuery={}

• why REST why not SOAP / RPC / ...
• why GET, why not POST
• naming convention

API: input & output (interface)

Protocol: how the communication happens (REST / ...)

Data Source & Flow

Where does the list of suggestions come from?

Users are constantly searching on Google.

Every time a user makes a search (search_query)

• this search_query goes to the /search microservice
• search microservice will return the relevant web-results
• (async) the search microservice will inform the /typeahead microservice that this search has been made (pass the search_query)
• the /typeahead service can store this search_query to populate its suggestions list

Non-Functional Requirements (NFR)

(design goals)

PACELC

Consistency vs Availability

Do NOT jump to an answer

Q: What is the data ?

Past search queries and their corresponding counts.

Q: What does eventual consistency mean in this context ?

When is the data changing?

Everytime someone makes a search, the count of some entry changes.

Everytime someone makes a search, the top-5 relevant results for some typeahead partial_query changes.

It is possible for the search-count to reflect in a delayed manner in the top-5 results.

For some time, it is possible that the true count of Query1 > Query2, but we still show Query2 before Query1 in the typeahead suggestions.

Q: Can we afford stale reads in this situation?

Yes, that's okay

• because the user doesn't really know (or care about) the true search counts
• we don't necessarily need to maintain a strict order in the typeahead suggestions

• it is okay for a few good suggestions to not be shown, as long as the ones shown as also good enough

Q: What does data loss mean in this context ?

Data loss would happen if someone has searched for a query, but for whatever reason, we were not able to increment the count for that query (query didn't get logged).

The counts will be off by a small amount.

Q: Can we afford data loss in this situation?

Yes, that's okay.

(same reasons as above)

Consistency vs Latency

What are our latency requirements?

Ultra-low latency - literally competing with the user's typing speed!

each typeahead query to take < 10ms

(this doesn't include the round trip - that depends on the user's distance from the servers - don't have much control over that - only solution for that is to have geolocated servers)

Others

• Security: do NOT do this unless you're a security expert

• 99% of all security issues happen because non-security expert devs try to do security

• Observability
• Rate Limits
• Idempotency
• Delivery Guarantees

Scale Estimation

The scale will dictate our design choices

Goals

• Amount of Data

• Is sharding needed?

• Amount of Load

• Requests per second (for each API)

• Peak Load (vs avg load)
• Read-heavy / Write-heavy

All these things will help us guide our choice of database, cache, & sharding

Does accuracy matter?

No. Back-of-the-envelope estimates.

being off by a factor of 2 or 3 is okay.

Actual value: 100

You suggest: 50   okay

You suggest: 200  okay

You suggest: 10  not okay (off by a factor of 10)

However, any estimates that you make should be justified. Don't pull out numbers from thin air. You will have to make some assumptions - each assumption should be clearly stated as such.

How to start

Start by estimating the number of daily active users.

World Population: ~8 billion

Number of Internet Users: ~5 billion

India's Population: ~1.4 billion

USA's Population: ~350 million

Pareto Principle (the 80/20 rule)

Only 20% of your users will be active.

Can be extended to the 80-20-1 principle for social media

• 80% are just passively browsing
• 20% are interacting (comments, likes, shares)
• 1% are content creators (posts)

Estimates

assumption: Google has 5 billion users.

Daily Active Users (DAU): 20%

= 20% of 5 billion users

= 1 billion users

assumption: Number of searches per active-user per day: 20

Total number of searches / day

= (20 searches / user / day) * (1 billion users)

= 20 searches / day * 1 billion

= 20 billion searches / day

Avg. searches / second

= 20 billion searches / day

= 20 * 10^9 searches / (10^5 seconds)   (1 day = 86400 seconds ~ 10^5 seconds)

= 200,000 searches / second

Note: searches are going to search API, not the typeahead API

assumption: Number of typeahead queries per search query: 10

avg size of a search query is 10 letters

we will start showing suggestions after the first 3 letters

number of typeaheads per search would be (10 - 3) = 7  ~ 10

typeahead(...) API: requests / second

Everytime a user is searching for something, they will first type the query, and then they will search.

search_query: "why is the sky blue"

• typeahead("why")
• typeahead("why i")
• typeahead("why is")
• typeahead("why is t")
• typeahead("why is th")
• typeahead("why is the")
• typeahead("why is the s")
• ...
• typeahead("why is the sky blue")

= (200,000 searches / second) * (10 typeaheads / search) 

= 2 million typeaheads / second

log_search(...) API: requests / second

Every time a search is made, the /search microservice pings the /typeahead microservice

= 200,000 requests / second

Peak Load

= 5x the average load

= 5 * (2 million typeaheads / second)

= 10 million typeaheads / second

Amount of Data

What's the data?

Past search queries & their counts

Avg. size of search query: 10 letters  (made this assumption earlier)

How many entries in this table?

Should we say that for each search that happens, we will have an entry in this table?

No. Because for new searches, we're adding entries

But for queries that have already been searched earlier, we're just updating the counts

The number of entries in the table will depend on the number of "unique" (never seen before in the history of Google) search queries that happen

assumption: % of search queries are new (never seen before) = 0.1%

assumption: % of search queries are new (never seen before) = 10%

number of new entries / day

= 10 % of (20 billion searches / day)

= 2 billion entries per day

amount of data / day

= (10 bytes / entry) * (2 billion entries / day)

= 20 GB / day

total amount of data (over 20 years)

= (20 GB / day) * (20 years)

= (20 GB / day) * (20 * 400 days)     (365 ~= 400)

= 16 * 10^4 GB

= 160 TB

Can this amount of data fit on a single server?

Probably yes, with modern storage.

But, will a single server be able to handle 10 million requests / second?

Absolutely no!

We need sharding!

Read Heavy / Write Heavy?

typeahead => read query => 2 million requests / second

log_search => write query => 200,000 requests / second

reads are 10x more than writes

We will call this read heavy, because even though the system has to handle lots of writes too, it is dominated by reads.

Whenever you've read heavy systems & the writes are also significant

• you can absorb your reads in a cache
• optimize your DB for writes

No database system is optimized for both reads & writes (that's impossible)